package flp;

import flp.problem.*;
import flp.exceptions.*;
import flp.solvers.genetic.GeneticSolver;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Klasa reprezentujaca layout.
 *
 * @author Ania i Pipen
 */

public class Layout implements Cloneable, Comparable {
   
    //rozmiar layoutu
    private int size;
    /**Koszt layoutu - null jesli niepoliczony.*/
    protected Integer cost = null;
    /**Tablica building site'ow.*/
    protected Usage[] places;
    /**Problem do ktorego ten Layout jest rozwiazaniem.*/
    protected ProblemInstance solutionTo;
    /* Ilość prob wylosowania poprawnego miejsca dla danego facility, po przekroczeniu rzucamy wyjatkiem */
    static private final int MAX_ITERATIONS = 5000;
    /*Ilość prób wygenerowania całego Layoutu od nowa, w przypadku gdy nie mozna znalezc juz miejsca dla Facility*/
    static private final int MAX_TRIES = 1500;

    public enum CostFunction{
        GREEDY, GREEDY_TC_FAVOURING, DAGSP, RANDOM_CHOICE, RANDOM_CHOICE_TC_FAVOURING;
        
        private static CostFunction defaultFunction = DAGSP;
        
        public static CostFunction getDefault()
        {
            return defaultFunction;
        }
        
        public static void setDefault(CostFunction function)
        {
            defaultFunction = function;
        }
     }
    
    // skoro getCost jest leniwy ale TYLKO wtedy, gdy poprzedni koszt policzono
    // z uzyciem tego samego algorytmu
    CostFunction currentMethod = null;
    
    /**
     * Konstruktor tworzacy nowy, losowy Layout, zgodny z wymaganiami zawartymi w ProblemInstance.
     * 
     * @param problem Zadany Facility Layout Problem.
     * @author Pipen 
     */
    
    private Layout(ProblemInstance problem) throws LayoutBuildException {
        
        solutionTo = problem;
        size = problem.getBuildingSitesCount();
        places = new Usage[size];
        
        int possibleFacilities = problem.getRiverFacilitiesCount();     //ile rodzajow budynkow mamy 
        BuildingConstraints bc = solutionTo.getConstraints();           //struktura do sprawdzania constraintsow
        Random rnd = new Random();
       
        boolean clearAndBeginOnceAgain = true;     //wyczysc layout i tworz od nowa
        int newStarts = 0;                         //zlicza ile razy zaczynalismy od nowa
        
        while(clearAndBeginOnceAgain && newStarts++ < MAX_TRIES) {
           
           //wyczyszczenie Layoutu i zaczęcie rozmieszczania od nowa  
           if(clearAndBeginOnceAgain ) {  
                  for (int i=0; i<size; i++) 
                     places[i] = null;
            }
            clearAndBeginOnceAgain = false;
            int iter = 0;       //duze porty numerujemy od 0
            int failsafe = 0;   //wyjscie bezpieczenta po określonej liczbie iteracji

            // INBOUNDY
            while(iter < possibleFacilities) {
                
              List<Integer> index = new LinkedList<Integer>();   //lista miejsc gdzie mozna postawic ten inbound
              InboundUsage in = new InboundUsage(iter);
              for(int i = 0; i < size; i++) {
                  Assignment assignment = new Assignment(i, in); 
                  if (bc.isLegal(assignment) && places[i] == null)
                      index.add(i);
              }
              //System.out.println("mozna postawic: " + index.size() +" inboundow "  + index.isEmpty());
              int requiredCapacity = problem.getRequiredInboundCapacity(iter);
              //System.out.println("req"+iter+": "+problem.getRequiredInboundCapacity(iter));
              int capacity = 0;  
              int range = index.size();
              while(capacity < requiredCapacity && failsafe++ < MAX_ITERATIONS) {
                 if(index.isEmpty()) throw new LayoutBuildException("Constructor : Too few Inbounds Allowed!");
                 int random = rnd.nextInt(range); 
                 int placeNo = index.get(random);                                     //gwarancja ze place jest dozwolone
                 index.remove(random);
                 range--;
                 places[placeNo] = in;
                 capacity += solutionTo.getBuildingSite(placeNo).getBaseSimulationTimeVolumenLimit();
                 //System.out.println("now: "+capacity);
              }
              iter++;
            } //------
            
            //OUTBOUNDY
            iter = 0;
            while(iter < possibleFacilities) {
                
                 List<Integer> index = new LinkedList<Integer>();   //lista miejsc gdzie mozna postawic ten inbound
                 OutboundUsage out = new OutboundUsage(iter);
                 for(int i = 0; i < size; i++) {
                     Assignment assignment = new Assignment(i, out); 
                     if (bc.isLegal(assignment) && places[i] == null)
                         index.add(i);
                 }
                 //System.out.println("mozna postawic: " + index.size() +" outboundow  "  + index.isEmpty());
                 int requiredCapacity = problem.getRequiredOutboundCapacity(iter);
                 int capacity = 0;  
                 int range = index.size();
                 while(capacity < requiredCapacity && failsafe++ < MAX_ITERATIONS) { 
                     if(index.isEmpty()) { failsafe = MAX_ITERATIONS;  }            //wyskoczenie z pętli i zaczęcie od nowa
                     else {
                        int random = rnd.nextInt(range); 
                        int placeNo = index.get(random);
                        index.remove(random);
                        range--;
                        places[placeNo] = out;
                        capacity += solutionTo.getBuildingSite(placeNo).getBaseSimulationTimeVolumenLimit();
                     }
                 }
                 iter++;
            }//-----
            
            //MYJNIE
            if(failsafe < MAX_ITERATIONS) {
                
            List<Integer> index = new LinkedList<Integer>();   //lista miejsc gdzie mozna postawic ten inbound
            CleaningUsage cleaning = new CleaningUsage();
            for(int i = 0; i < size; i++) {
                Assignment assignment = new Assignment(i, cleaning); 
                if (bc.isLegal(assignment) && places[i] == null)
                     index.add(i);
            }
            //System.out.println("mozna postawic: " + index.size() +" myjni  "  + index.isEmpty());
            int requiredCapacity = problem.getRequiredCleaningCapacity();
            int capacity = 0;  
            int range = index.size();
            while(capacity < requiredCapacity && failsafe++ < MAX_ITERATIONS){
                if(index.isEmpty()) { failsafe = MAX_ITERATIONS;   }
                else {
                    int random = rnd.nextInt(range);
                    int placeNo = index.get(random);
                    index.remove(random);
                    range--;
                    places[placeNo] = cleaning;
                    capacity += solutionTo.getBuildingSite(placeNo).getBaseSimulationTimeVolumenLimit();
                }    
            }
            //nic więcej nie dolosowywujemy - facilities jest tyle ile ma być
            }
            //System.out.println("dane : fail:" + failsafe);
            if(failsafe++ >= MAX_ITERATIONS) clearAndBeginOnceAgain = true; //ustawienie flagi - zaczynamy od nowa
         }//petla glowna

         //wyjście bezpieczeństwa, po osiagnieciu odpowiednio duzej liczby iteracji wyrzuca wyjątek
         if(newStarts++ >= MAX_TRIES) throw new LayoutBuildException("Constructor : I cannot create any legal Layout!");
    } 
    
    /**
     * Factory method zwracajaca losowy Layout dla zadanego Problemu.
     * 
     * @param problem Dane dla jakich Layout jest rozwiazaniem.
     * @return Nowy, losowy Layout zgodny z wszystkimi wymaganiami problemu podanego w argumencie.
     * @throws flp.exceptions.LayoutBuildException
     */
    
    public static Layout getInstance(ProblemInstance problem) throws LayoutBuildException {
        return new Layout(problem);
    }
    
    /**
     * Konstruktor pomocniczy, zwracajacy nowy Layout, utworzony na podstawie tablicy Usages.
     * Nie ma gwarancji, ze jest on zgodny z wymaganiami zawartymi w problem.
     * 
     * @param places Tablica zastosowan budynkow, na podstawie ktorej wygenerowany zostanie layout.
     * @param problem Problem, ktorego rozwiazaniem bedzie dany layout.
     */
    
    public Layout(Usage[] places, ProblemInstance problem)
    {
        this.places = places;
        this.size = places.length;
        this.solutionTo = problem;
    }
    
    @Override
    public Layout clone()
    {
        Usage[] kopia = new Usage[size];
        for(int i=0; i<size; i++) {
            kopia[i] = places[i];
        }
        Layout clone = new Layout(kopia, solutionTo);
        return clone;
    }

    /**
     * Proksy dla funkcji kosztu z wykorzystaniem domyslnej funkcji.
     * 
     * @return Koszt rozmieszczenia budynkow.
     * @throws flp.exceptions.FlowImpossibleException
     */
    
    public int getCost() throws FlowImpossibleException
    {
        return getCost(CostFunction.getDefault());
    }
    
    /**
     * Metoda wybierajaca w zaleznosci od parametru odpowiedni wariant funkcji kosztu
     * i przekazujaca obliczony przez ta funkcja koszt jako wartosc zwracana.
     * 
     * @throws FlowImpossibleException
     * @return Liczba calkowita bedaca oszacowanym kosztem biezacego Layoutu.
     */
    
    public int getCost(CostFunction fun) throws FlowImpossibleException{
        
        // zachowanie leniwosci, no ale na pewnych warunkach
        if (currentMethod != fun || cost == null)
        {
            currentMethod = fun;
            switch(fun)
            {
                case GREEDY:
                    cost = greedyCostFinder();
                    break;
                case GREEDY_TC_FAVOURING:
                    cost = greedyTCFavouringCostFinder();
                    break;
                case DAGSP:
                    cost = DAGSPCostFinder();
                    break;
                case RANDOM_CHOICE:
                    cost = RandomChoiceDAGSPCostFinder();
                    break;
                default:
                    cost = RandomChoiceTCFavouringDAGSPCostFinder();
                    break;                                  
            }            
        }   
        return cost;      
    }
    
    /** 
     * Zachlanna funkcja kosztu, opiera sie na sekwencyjnym wybieraniu najtanszych
     * krawedzi najpierw dla relacji NC, a pozniej dla TC.
     * 
     * @author freeze
     * @return Szacowany koszt optymalnego przeplywu barek.
     * @throws flp.exceptions.FlowImpossibleException
     */
    
    private int greedyCostFinder() throws FlowImpossibleException
    {    
        // robimy osobna tablice, gdyz to bedzie lokalna przepustowosc
        int [] capacity = new int[solutionTo.getBuildingSitesCount()];
        
        for(int i = 0; i < solutionTo.getBuildingSitesCount(); ++ i)
        {
            capacity[i] = solutionTo.getBuildingSite(i).getBaseSimulationTimeVolumenLimit();        
            
        }
        int globalCost = 0;
           
        //liczymy dla wszystkich relacji
        for(int i = 0; i<solutionTo.getRiverFacilitiesCount() ; ++ i) {
            for (int j = 0; j<solutionTo.getRiverFacilitiesCount(); ++ j) {             
                List<Integer> inbounds = new LinkedList<Integer>();
                List<Integer> outbounds = new LinkedList<Integer>();
                List<Integer> cleanings = new LinkedList<Integer>();
 
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof CleaningUsage) 
                         cleanings.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof InboundUsage && ((InboundUsage)places[it]).getSourceRiverFacilityID()==i) 
                         inbounds.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(this.places[it] instanceof OutboundUsage && ((OutboundUsage)places[it]).getTargetRiverFacilityID()==j) 
                         outbounds.add(new Integer(it));
                 }            
                 
                // do przepchania, wymagajace czyszczenia
                 int TC = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, true);
                 
                 // barki do przepchania bez czyszczenia
                 int NC = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, false);
                 
                 int currentTC = 0;
                 int currentNC = 0;
                            
                 
                 while( currentNC < NC )
                 {
                     //wyszukiwanie najlepszej drogi
                     // sciezka prosto z inbounda do outbounda 
                    int mink = -1;
                    int minl = -1;
                   
                     for(int k:inbounds)
                     {
                         for(int l:outbounds)
                         {
                             
                             
                              if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 ||
                                    solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                                    solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                                    {
                                           mink=k;
                                           minl=l;
                                                                                 
                                    }
                         }
                                 
                     }
                     
                     if(mink==-1 || minl==-1)
                         throw new FlowImpossibleException();
                     int flow = Math.min(capacity[mink], capacity[minl]);
                     flow = Math.min(flow, NC-currentNC);
                     currentNC+=flow;
                    
                     capacity[mink]-=flow;
                     capacity[minl]-=flow;
                     globalCost+=flow*solutionTo.getBuildingSite(mink).getTransferToCost(minl);                                   
               
                 }
                // policzone Non-Cleaningi, teraz liczymy TC
                 int sum = 0;
                 for(int k:inbounds)
                     sum+=capacity[k];
                 
              //  System.out.println("TC: " + TC);
                //System.out.println("pojemnosc: " + sum);
                 while( currentTC < TC)
                 {                     
                        int mink = -1;
                        int minl = -1;
                        int minm = -1;
                        for(int k:inbounds)
                        {
                         for(int l:cleanings)
                             if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 || 
                                    solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                                    solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                                    {
                                           mink=k;
                                           minl=l;
                                    }
                                 
                        }
                        for(int m:outbounds)
                            if( capacity[m] > 0 && 
                            ( minm == -1 || solutionTo.getBuildingSite(minl).getTransferToCost(m) < 
                                    solutionTo.getBuildingSite(minl).getTransferToCost(minm))
                            )
                            {
                                minm = m;
                            }
                        
                        // update'owanie przeplywu
                        if(mink==-1 || minl==-1)
                            throw new FlowImpossibleException();
                        int flow = Math.min(capacity[mink], capacity[minl]);
                        flow = Math.min(flow, capacity[minm]);
                        flow = Math.min(flow, TC - currentTC);
                        currentTC+=flow;
                        capacity[mink]-=flow;
                        capacity[minl]-=flow;
                        capacity[minm]-=flow;
                        globalCost+=flow*(solutionTo.getBuildingSite(mink).getTransferToCost(minl)
                                            + solutionTo.getBuildingSite(minl).getTransferToCost(minm));                              
                       
                 }
                   
            }
        }
         for(int i=0; i<solutionTo.getRiverFacilitiesCount(); ++i) {
           if(this.places[i] instanceof CleaningUsage) 
               globalCost += solutionTo.getBuildingSite(i).getCleaningSiteSettingCost();
        }
        
        return globalCost;
        
    }
    /**
     * Metoda analogiczna do greedy, przetwarza jednak wpierw
     * relacje TC.
     * 
     * @author freeze
     * @return Szacowany koszt natanszego przeplywu.
     * @throws flp.exceptions.FlowImpossibleException
     */
     
    private int greedyTCFavouringCostFinder() throws FlowImpossibleException
    {    
        // robimy osobna tablice, gdyz to bedzie lokalna przepustowosc
        int [] capacity = new int[solutionTo.getBuildingSitesCount()];
        
        for(int i = 0; i < solutionTo.getBuildingSitesCount(); ++ i)
        {
            capacity[i] = solutionTo.getBuildingSite(i).getBaseSimulationTimeVolumenLimit();        
            
        }
        int globalCost = 0;
           
        //liczymy dla wszystkich relacji
        for(int i = 0; i<solutionTo.getRiverFacilitiesCount() ; ++ i) {
            for (int j = 0; j<solutionTo.getRiverFacilitiesCount(); ++ j) {             
                List<Integer> inbounds = new LinkedList<Integer>();
                List<Integer> outbounds = new LinkedList<Integer>();
                List<Integer> cleanings = new LinkedList<Integer>();
 
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof CleaningUsage) 
                         cleanings.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof InboundUsage && ((InboundUsage)places[it]).getSourceRiverFacilityID()==i) 
                         inbounds.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(this.places[it] instanceof OutboundUsage && ((OutboundUsage)places[it]).getTargetRiverFacilityID()==j) 
                         outbounds.add(new Integer(it));
                 }            
                 
                // do przepchania, wymagajace czyszczenia
                 int TC = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, true);
                 
                 // barki do przepchania bez czyszczenia
                 int NC = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, false);
                 
                 int currentTC = 0;
                 int currentNC = 0;                        
                                         
                 while( currentTC < TC)
                 {                     
                        int mink = -1;
                        int minl = -1;
                        int minm = -1;
                        for(int k:inbounds)
                        {
                         for(int l:cleanings)
                             if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 || 
                                    solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                                    solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                                    {
                                           mink=k;
                                           minl=l;
                                    }
                                 
                        }
                        for(int m:outbounds)
                            if( capacity[m] > 0 && 
                            ( minm == -1 || solutionTo.getBuildingSite(minl).getTransferToCost(m) < 
                                    solutionTo.getBuildingSite(minl).getTransferToCost(minm))
                            )
                            {
                                minm = m;
                            }
                        
                        // update'owanie przeplywu
                        
                        int flow = Math.min(capacity[mink], capacity[minl]);
                        flow = Math.min(flow, capacity[minm]);
                        flow = Math.min(flow, TC - currentTC);
                        currentTC+=flow;
                        capacity[mink]-=flow;
                        capacity[minl]-=flow;
                        capacity[minm]-=flow;
                        globalCost+=flow*(solutionTo.getBuildingSite(mink).getTransferToCost(minl)
                                            + solutionTo.getBuildingSite(minl).getTransferToCost(minm));                              
                       
                 }
                 while( currentNC < NC )
                 {
                     //wyszukiwanie najlepszej drogi
                     // sciezka prosto z inbounda do outbounda 
                    int mink = -1;
                    int minl = -1;
                   
                    for(int k:inbounds)
                     {
                         for(int l:outbounds)
                         {                                                      
                              if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 ||
                                    solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                                    solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                                    {
                                           mink=k;
                                           minl=l;
                                                                                 
                                    }
                         }
                                 
                     }
                    
                    if(mink==-1 || minl==-1)
                        throw new FlowImpossibleException();
                     
                     int flow = Math.min(capacity[mink], capacity[minl]);
                     flow = Math.min(flow, NC-currentNC);
                     currentNC+=flow;
                    
                     capacity[mink]-=flow;
                     capacity[minl]-=flow;
                     globalCost+=flow*solutionTo.getBuildingSite(mink).getTransferToCost(minl);                                   
               
                 }
                   
            }
        }
         for(int i=0; i<solutionTo.getRiverFacilitiesCount(); ++i) {
           if(this.places[i] instanceof CleaningUsage) 
               globalCost += solutionTo.getBuildingSite(i).getCleaningSiteSettingCost();
        }
        
        return globalCost;
        
    }
    
    /**
     * Metoda wykorzystuje wlasnosc acyklicznosci grafu powstalego z Layoutu i 
     * przyspiesza tym obliczenia, czyniac je bardziej efektywnymi. Dodatkowo
     * wyszukujemy w danym kroku prawdziwie najkrotsza sciezke dla danej relacji,
     * nie opieramy sie bowiem tylko i wylacznie na wyszukiwaniu lokalnie
     * najtanszej krawedzi 
     * 
     * @author freeze
     * @return Szacowany koszt natanszego przeplywu.
     * @throws flp.exceptions.FlowImpossibleException
     */
    
    private int DAGSPCostFinder() throws FlowImpossibleException
    {
         // robimy osobna tablice, gdyz to bedzie lokalna przepustowosc
        int [] capacity = new int[solutionTo.getBuildingSitesCount()];
        int [] reachingCost = new int[solutionTo.getBuildingSitesCount()];
        int [] pred = new int[solutionTo.getBuildingSitesCount()];
        
        
        for(int i = 0; i < solutionTo.getBuildingSitesCount(); ++ i)
        {
            capacity[i] = solutionTo.getBuildingSite(i).getBaseSimulationTimeVolumenLimit();                    
        }
        int globalCost = 0;
           
        //liczymy dla wszystkich relacji
        for(int i = 0; i<solutionTo.getRiverFacilitiesCount() ; ++ i) {
            for (int j = 0; j<solutionTo.getRiverFacilitiesCount(); ++ j) {             
                List<Integer> inbounds = new LinkedList<Integer>();
                List<Integer> outbounds = new LinkedList<Integer>();
                List<Integer> cleanings = new LinkedList<Integer>();
 
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof CleaningUsage) 
                         cleanings.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof InboundUsage && ((InboundUsage)places[it]).getSourceRiverFacilityID()==i) 
                         inbounds.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(this.places[it] instanceof OutboundUsage && ((OutboundUsage)places[it]).getTargetRiverFacilityID()==j) 
                         outbounds.add(new Integer(it));
                 }            
                 
                // do przepchania, wymagajace czyszczenia
                 int TC = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, true);
                 
                 // barki do przepchania bez czyszczenia
                 int NC = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, false);
                 
                 int currentTC = 0;
                 int currentNC = 0;
                 
                 // roznica taka, ze tutaj dzialamy na zasadzie djikstry i powinnismy zawsze
                 //dostawac lepsze rozwiazanie
                 while( currentTC < TC)
                 {
                     for(int p = 0; p < solutionTo.getBuildingSitesCount(); ++ p)
                        reachingCost[p] = Integer.MAX_VALUE;            
                     
                        for(int k:inbounds)
                        {
                         for(int l:cleanings)
                             if( capacity[k] > 0 && capacity[l] > 0)
                                    {
                                    // RELAX :)
                                       if( reachingCost[l] > solutionTo.getBuildingSite(k).getTransferToCost(l))
                                       {
                                           reachingCost[l] = solutionTo.getBuildingSite(k).getTransferToCost(l);
                                           pred[l] = k;
                                       }                                     
                                    }                               
                        }
                        
                        for(int k:cleanings)
                            for(int m:outbounds)
                                if( capacity[m] > 0 && capacity[k] > 0)
                                {
                                    //RELAX
                                    if( reachingCost[m] > reachingCost[k] + solutionTo.getBuildingSite(k).getTransferToCost(m))
                                    {
                                        reachingCost[m] = reachingCost[k] + solutionTo.getBuildingSite(k).getTransferToCost(m);
                                        pred[m] = k;
                                    }
                                }
                            
                                            
                         // restore rozwiazania na podstawie tablicy poprzednikow
                         int clean, in, out=outbounds.get(0);
                         for(int z:outbounds)
                             if( reachingCost[z] < reachingCost[out])
                                 out = z;
                         if( reachingCost[out] == Integer.MAX_VALUE)
                             throw new FlowImpossibleException();
                         clean = pred[out];
                         in = pred[clean];
                         
                        // update'owanie przeplywu
                        int cap = Math.min(capacity[in], capacity[clean]);
                        cap = Math.min(cap, capacity[out]);
                        cap = Math.min(cap, TC - currentTC);
                        
                        currentTC+=cap;
                        capacity[in]-=cap;
                        capacity[out]-=cap;
                        capacity[clean]-=cap;
                        globalCost+=cap*reachingCost[out];
                 }           
                 
                 while( currentNC < NC )
                 {
                     //wyszukiwanie najlepszej drogi
                     // sciezka prosto z inbounda do outbounda 
                    int mink = -1;
                    int minl = -1;
                   
                     for(int k:inbounds)
                     {
                         for(int l:outbounds)
                         {                                                        
                              if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 ||
                                    solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                                    solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                                    {
                                           mink=k;
                                           minl=l;
                                                                                 
                                    }
                         }
                                 
                     }
                     if(mink == -1 || minl == -1)
                         throw new FlowImpossibleException();
                     int flow = Math.min(capacity[mink], capacity[minl]);
                     flow = Math.min(flow, NC-currentNC);
                     currentNC+=flow;
                    
                     capacity[mink]-=flow;
                     capacity[minl]-=flow;
                     globalCost+=flow*solutionTo.getBuildingSite(mink).getTransferToCost(minl);                                   
               
                 }
           
            }
        }
         for(int i=0; i<solutionTo.getRiverFacilitiesCount(); ++i) {
           if(this.places[i] instanceof CleaningUsage) 
               globalCost += solutionTo.getBuildingSite(i).getCleaningSiteSettingCost();
        }
        
        return globalCost;
    }
    
    /**
     * Globalnie dzialajaca metoda znajdowania kosztu.
     * W kazdym kroku losujemy relacje, dla której istnieje niespelnione
     * zapotrzebowanie (wraz z informacja o ewentualnym wyslaniu barki do myjni),
     * po czym znajdujemy najkrotsza sciezke dla tej relacji i aktualizujemy graf,
     * az do spelniania calego globalnego zapotrzebowania. Rozwiazanie
     * cechuje sie mniejsza wariancja w stosunku do uzytych metod deterministycznych.
     * 
     * @author freeze
     * @throws flp.exceptions.FlowImpossibleException
     * @return Szacowany koszt natanszego przeplywu.
     * */
    
    private int RandomChoiceDAGSPCostFinder() throws FlowImpossibleException
    {
        int globalCost = 0;        
        int [] capacity = new int[solutionTo.getBuildingSitesCount()];
        int [] reachingCost = new int[solutionTo.getBuildingSitesCount()];
        int [] pred = new int[solutionTo.getBuildingSitesCount()];
        
        // pojemnosc jest wspolna dla wszystkich building site'ow
        for(int i = 0; i < solutionTo.getBuildingSitesCount(); ++ i)
        {
            capacity[i] = solutionTo.getBuildingSite(i).getBaseSimulationTimeVolumenLimit();                    
        }
       // tablice aktualnego zapotrzebowania, ktore musimy na biezaco aktualizowac,
       // zeby nie wpychac barek, gdzie ich nie trzeba
        int [][] globalNCDemand = new int[solutionTo.getRiverFacilitiesCount()][solutionTo.getRiverFacilitiesCount()];
        int [][] globalTCDemand = new int[solutionTo.getRiverFacilitiesCount()][solutionTo.getRiverFacilitiesCount()];
        
        // globalne niespelnione zapotrzebowanie, jako warunek konca petli
        int unfulfilledDemand = 0;
        
        for(int i = 0; i<solutionTo.getRiverFacilitiesCount(); ++ i)
          for(int j = 0; j<solutionTo.getRiverFacilitiesCount(); ++ j)
          {
             globalNCDemand[i][j] = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, false);
             globalTCDemand[i][j] = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, true);
             unfulfilledDemand+=globalNCDemand[i][j]+globalTCDemand[i][j];             
          }
        
        while( unfulfilledDemand > 0 )
        {
            // losujemy typ trasy, dla jakiej chcemy znalezc optymalna sciezke;
            boolean legal = false;
            boolean toClean = false;
            int i = 0, j = 0;
            
            while( !legal )
            {
                Random rnd = new Random();
                if( rnd.nextInt(2) == 0)
                    toClean = false;
                else 
                    toClean = true;
                
                i=rnd.nextInt(solutionTo.getRiverFacilitiesCount());
                j=rnd.nextInt(solutionTo.getRiverFacilitiesCount());
                
                // sprawdzamy czy jest tam co przepychac
                
                if( toClean )
                {
                    if( globalTCDemand[i][j] > 0 )
                        legal = true;
                }
                else
                {
                    if(globalNCDemand[i][j] > 0)
                        legal = true;
                }
               
            }
            
            // mamy juz to co chcemy, czyli relacje + toClean or not toClean
                List<Integer> inbounds = new LinkedList<Integer>();
                List<Integer> outbounds = new LinkedList<Integer>();
                List<Integer> cleanings = new LinkedList<Integer>();
 
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof CleaningUsage) 
                         cleanings.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof InboundUsage && ((InboundUsage)places[it]).getSourceRiverFacilityID()==i) 
                         inbounds.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(this.places[it] instanceof OutboundUsage && ((OutboundUsage)places[it]).getTargetRiverFacilityID()==j) 
                         outbounds.add(new Integer(it));
                 }   
                
            if( toClean )
            {
                      for(int p = 0; p < solutionTo.getBuildingSitesCount(); ++ p)
                        reachingCost[p] = Integer.MAX_VALUE;            
                     
                        for(int k:inbounds)
                        {
                         for(int l:cleanings)
                             if( capacity[k] > 0 && capacity[l] > 0)
                                    {
                                    // RELAX :)
                                       if( reachingCost[l] > solutionTo.getBuildingSite(k).getTransferToCost(l))
                                       {
                                           reachingCost[l] = solutionTo.getBuildingSite(k).getTransferToCost(l);
                                           pred[l] = k;
                                       }                                     
                                    }                               
                        }
                        
                        for(int k:cleanings)
                            for(int m:outbounds)
                                if( capacity[m] > 0 && capacity[k] > 0)
                                {
                                    //RELAX
                                    if( reachingCost[m] > reachingCost[k] + solutionTo.getBuildingSite(k).getTransferToCost(m))
                                    {
                                        reachingCost[m] = reachingCost[k] + solutionTo.getBuildingSite(k).getTransferToCost(m);
                                        pred[m] = k;
                                    }
                                }
                            
                                            
                         // restore rozwiazania na podstawie tablicy poprzednikow
                         int clean, in, out=outbounds.get(0);
                         for(int z:outbounds)
                             if( reachingCost[z] < reachingCost[out])
                                 out = z;
                         if(reachingCost[out] == Integer.MAX_VALUE)
                             throw new FlowImpossibleException();
                         clean = pred[out];
                         in = pred[clean];
                         
                        // update'owanie przeplywu
                        int cap = Math.min(capacity[in], capacity[clean]);
                        cap = Math.min(cap, capacity[out]);
                        cap = Math.min(cap, globalTCDemand[i][j]);
                        
                        globalTCDemand[i][j]-=cap;
                        capacity[in]-=cap;
                        capacity[out]-=cap;
                        capacity[clean]-=cap;
                        globalCost+=cap*reachingCost[out];
                        unfulfilledDemand-=cap;
            }
            else
            {
                    int mink = -1;
                    int minl = -1;
                    
                    for(int k:inbounds)
                     {
                         for(int l:outbounds)
                         {                                 
                               if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 ||
                                    solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                                    solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                                    {
                                         
                                           mink=k;
                                           minl=l;                                                                                 
                                    }
                         }
                                 
                     }                  
                     
                     if( mink==-1 || minl == -1)
                         throw new FlowImpossibleException();
                     int flow = Math.min(capacity[mink], capacity[minl]);
                     flow = Math.min(flow, globalNCDemand[i][j]);
                     globalNCDemand[i][j]-=flow;
                     unfulfilledDemand -= flow;
                     capacity[mink]-=flow;
                     capacity[minl]-=flow;
                     globalCost+=flow*solutionTo.getBuildingSite(mink).getTransferToCost(minl);                                                  
            }
            
        }
        
        
         for(int i=0; i<solutionTo.getRiverFacilitiesCount(); ++i) {
           if(this.places[i] instanceof CleaningUsage) 
               globalCost += solutionTo.getBuildingSite(i).getCleaningSiteSettingCost();
         }
        return globalCost;
        
    }
    
      /**
     * Globalnie dzialająca metoda znajdowania kosztu.
     * W kazdym kroku losujemy relacje, dla ktorej istnieje niespelnione
     * zapotrzebowanie, po czym znajdujemy najkrotszą sciezkę dla tej relacji i aktualizujemy graf,
     * az do spelniania calego zapotrzebowania TC. Nastepnie powtarzamy czynnosci
     * dla zapotrzebowania NC.
     * 
     * @author freeze
     * @throws flp.exceptions.FlowImpossibleException
     * @return Szacowany koszt najtanszego przeplywu.
     * */
    
    private int RandomChoiceTCFavouringDAGSPCostFinder() throws FlowImpossibleException
    {
        int globalCost = 0;        
        int [] capacity = new int[solutionTo.getBuildingSitesCount()];
        int [] reachingCost = new int[solutionTo.getBuildingSitesCount()];
        int [] pred = new int[solutionTo.getBuildingSitesCount()];
        
        // pojemnosc jest wspolna dla wszystkich building site'ow
        for(int i = 0; i < solutionTo.getBuildingSitesCount(); ++ i)
        {
            capacity[i] = solutionTo.getBuildingSite(i).getBaseSimulationTimeVolumenLimit();                    
        }
       // tablice aktualnego zapotrzebowania, ktore musimy na biezaco aktualizowac,
       // zeby nie wpychac barek, gdzie ich nie trzeba
        int [][] globalNCDemand = new int[solutionTo.getRiverFacilitiesCount()][solutionTo.getRiverFacilitiesCount()];
        int [][] globalTCDemand = new int[solutionTo.getRiverFacilitiesCount()][solutionTo.getRiverFacilitiesCount()];
        
        // globalne niespelnione zapotrzebowanie, jako warunek konca petli
        int unfulfilledTCDemand = 0;
        int unfulfilledNCDemand = 0;
        
        for(int i = 0; i<solutionTo.getRiverFacilitiesCount(); ++ i)
          for(int j = 0; j<solutionTo.getRiverFacilitiesCount(); ++ j)
          {
             globalNCDemand[i][j] = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, false);
             globalTCDemand[i][j] = solutionTo.getRiverFacility(i).getBargesRequiredToNumber(j, true);
             unfulfilledTCDemand+=globalTCDemand[i][j];
             unfulfilledNCDemand+=globalNCDemand[i][j];
          }
        
        // najpierw myjniowo  
        while( unfulfilledTCDemand > 0 )
        {
            // losujemy typ trasy, dla jakiej chcemy znalezc optymalna sciezke;
            boolean legal = false;
        
            int i = 0, j = 0;
            
            while( !legal )
            {
                Random rnd = new Random();
                i=rnd.nextInt(solutionTo.getRiverFacilitiesCount());
                j=rnd.nextInt(solutionTo.getRiverFacilitiesCount());
                
                // sprawdzamy czy jest tam co przepychac
                
                
                
                if( globalTCDemand[i][j] > 0 )
                      legal = true;
                
                
            }
            
                List<Integer> inbounds = new LinkedList<Integer>();
                List<Integer> outbounds = new LinkedList<Integer>();
                List<Integer> cleanings = new LinkedList<Integer>();
 
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof CleaningUsage) 
                         cleanings.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(places[it] instanceof InboundUsage && ((InboundUsage)places[it]).getSourceRiverFacilityID()==i) 
                         inbounds.add(new Integer(it));
                 }
                 for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                     if(this.places[it] instanceof OutboundUsage && ((OutboundUsage)places[it]).getTargetRiverFacilityID()==j) 
                         outbounds.add(new Integer(it));
                 }   
                
            
               for(int p = 0; p < solutionTo.getBuildingSitesCount(); ++ p)
                        reachingCost[p] = Integer.MAX_VALUE;            
                     
                        for(int k:inbounds)
                        {
                         for(int l:cleanings)
                             if( capacity[k] > 0 && capacity[l] > 0)
                                    {
                                    // RELAX :)
                                       if( reachingCost[l] > solutionTo.getBuildingSite(k).getTransferToCost(l))
                                       {
                                           reachingCost[l] = solutionTo.getBuildingSite(k).getTransferToCost(l);
                                           pred[l] = k;
                                       }                                     
                                    }                               
                        }
                        
                        for(int k:cleanings)
                            for(int m:outbounds)
                                if( capacity[m] > 0 && capacity[k] > 0)
                                {
                                    //RELAX
                                    if( reachingCost[m] > reachingCost[k] + solutionTo.getBuildingSite(k).getTransferToCost(m))
                                    {
                                        reachingCost[m] = reachingCost[k] + solutionTo.getBuildingSite(k).getTransferToCost(m);
                                        pred[m] = k;
                                    }
                                }
                            
                                            
                         // restore rozwiazania na podstawie tablicy poprzednikow
                         int clean, in, out=outbounds.get(0);
                         for(int z:outbounds)
                             if( reachingCost[z] < reachingCost[out])
                                 out = z;
                         if( reachingCost[out] == Integer.MAX_VALUE)
                             throw new FlowImpossibleException();
                         clean = pred[out];
                         in = pred[clean];
                         
                        // update'owanie przeplywu
                        int cap = Math.min(capacity[in], capacity[clean]);
                        cap = Math.min(cap, capacity[out]);
                        cap = Math.min(cap, globalTCDemand[i][j]);
                        
                        globalTCDemand[i][j]-=cap;
                        capacity[in]-=cap;
                        capacity[out]-=cap;
                        capacity[clean]-=cap;
                        globalCost+=cap*reachingCost[out];
                        unfulfilledTCDemand-=cap;
            }
        
            while( unfulfilledNCDemand > 0)            
            {
                
            // losujemy typ trasy, dla jakiej chcemy znalezc optymalna sciezke;
            boolean legal = false;
        
            int i = 0, j = 0;
            
            while( !legal )
            {
                Random rnd = new Random();
                i=rnd.nextInt(solutionTo.getRiverFacilitiesCount());
                j=rnd.nextInt(solutionTo.getRiverFacilitiesCount());
                
                // sprawdzamy czy jest tam co przepychac                              
                
                if( globalNCDemand[i][j] > 0 )
                      legal = true;                
                
            }
            
            List<Integer> inbounds = new LinkedList<Integer>();
            List<Integer> outbounds = new LinkedList<Integer>();

            for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                 if(places[it] instanceof InboundUsage && ((InboundUsage)places[it]).getSourceRiverFacilityID()==i) 
                     inbounds.add(new Integer(it));
            }
            for(int it=0; it<solutionTo.getBuildingSitesCount(); it++) {
                 if(this.places[it] instanceof OutboundUsage && ((OutboundUsage)places[it]).getTargetRiverFacilityID()==j) 
                     outbounds.add(new Integer(it));
            }   

            int mink = -1;
            int minl = -1;

            for(int k:inbounds)
            {
                 for(int l:outbounds)
                 {                                 
                       if( capacity[k] > 0 && capacity[l] > 0 && (mink==-1 ||
                            solutionTo.getBuildingSite(k).getTransferToCost(l) < 
                            solutionTo.getBuildingSite(mink).getTransferToCost(minl)))
                            {

                                   mink=k;
                                   minl=l;                                                                                 
                            }
                 }

            }

            if( mink==-1 || minl == -1)
                 throw new FlowImpossibleException();
            int flow = Math.min(capacity[mink], capacity[minl]);
            flow = Math.min(flow, globalNCDemand[i][j]);
            globalNCDemand[i][j]-=flow;
            unfulfilledNCDemand -= flow;
            capacity[mink]-=flow;
            capacity[minl]-=flow;
            globalCost+=flow*solutionTo.getBuildingSite(mink).getTransferToCost(minl);                                                  
        }            
        
        for(int i=0; i<solutionTo.getRiverFacilitiesCount(); ++i) {
           if(this.places[i] instanceof CleaningUsage) 
               globalCost += solutionTo.getBuildingSite(i).getCleaningSiteSettingCost();
        }
        return globalCost;
    }
    
    /**
     * Metoda sprawdzajaca poprawnosc layoutu.
     * 
     * @return Zwraca true jesli layout jest poprawny. 
     */
    
    public boolean checkCorrectness(){ 
        //1. sprawdzenie 1 - czy odpowiednie usage moga stac tam gdzie stoja
        BuildingConstraints bc = solutionTo.getConstraints();
        for(int i = 0; i<size; i++) {
            Assignment assignment = new Assignment(i,places[i]);
            if(bc.isLegal(assignment) == false)
                return false;
        }
        
        //2. sprawdzenie czy przepustowosc layoutu zaspokaja wymagania
        
        int capacity = 0; //maksymalna ilosc barek przeplywajacych pomiedzy dwoma konkretnymi portami 
        int requiredCapacity = 0;
        //INBOUNDY
        for (int i = 0; i < this.solutionTo.getRiverFacilitiesCount(); ++i) {
            capacity = 0;
            requiredCapacity = solutionTo.getRequiredInboundCapacity(i);
            
            //wyszukiwanie w layoucie wszystkich "i-tych" InboundUsage'ow i obliczanie ich przepustowosci
            for (int k = 0; k < size; ++k) {      
              if  (this.places[k] instanceof InboundUsage &&
                  (((InboundUsage)this.places[k]).getSourceRiverFacilityID()) == i)
                        capacity = capacity + this.solutionTo.getBuildingSite(k).getBaseSimulationTimeVolumenLimit();  
            }
            //jezeli odpowiednie inboundy nie moga obsluzyc wszystkich barek, layout jest niepoprawny 
            if(requiredCapacity > capacity)
                return false;      
        }       
        //OUTBOUNDY     
        for (int i = 0; i < this.solutionTo.getRiverFacilitiesCount(); ++i) {
            capacity = 0;
            requiredCapacity = solutionTo.getRequiredOutboundCapacity(i);
                      
            //wyszukiwanie w layoucie wszystkich "j-tych" OutboundUsage'ow i obliczanie ich przepustowosci
            for (int k = 0; k < size; ++k) {
                 if  (this.places[k] instanceof OutboundUsage &&
                        (((OutboundUsage)this.places[k]).getTargetRiverFacilityID() == i))
                            capacity = capacity + this.solutionTo.getBuildingSite(k).getBaseSimulationTimeVolumenLimit();  
            }
            //jezeli odpowiednie outboundy nie moga obsluzyc wszystkich barek, layout jest niepoprawny                 
            if(requiredCapacity > capacity)
                 return false;
        }
        //MYJNIE
        
        capacity = 0;
        requiredCapacity = solutionTo.getRequiredCleaningCapacity();

         //obliczanie przepustowosci wszystkich myjni
         for (int k = 0; k < size; ++k) {
            if  (this.places[k] instanceof CleaningUsage)
                    capacity = capacity + this.solutionTo.getBuildingSite(k).getBaseSimulationTimeVolumenLimit();  
        }    
         //jezeli myjnie nie moga obsluzyc wszystkich barek, layout jest niepoprawny                     
         if(requiredCapacity > capacity)
              return false;
        
        return true; // Layout poprawny
    }
    
    public ProblemInstance getProblem()
    {
        return solutionTo;
    }
    
    public int getSize(){
        return size;
    }
    
    public void setSize(int size){
        this.size = size; 
    }

    public Usage getPlace(int i) {
        return places[i];
    }
    
    public void setPlace(int i, Usage u) {
        places[i] = u;
        cost = null;    //to juz inny layout - resetuje koszt
    }
    
     /** Metoda porownuje koszty dwoch Layoutow,
      * jezeli layout w arg ma mniejszy koszt zwraca 1.
      * 
      * @param o Do czego jest porownywany biezacy Layout.
      * @param fun Jakiej funkcji uzyc do liczenia kosztu.
      * 
      * @return -1 jezeli biezacy Layout jest tanszy, 1 jezeli drozszy,
      * 0 jezeli ich koszt jest rowny, lub wystapil blad.
      **/
    
     public int compareTo(Object o, CostFunction fun) {
        try {

            if (this.getCost(fun) < ((Layout) o).getCost(fun)) {
                return -1;
            } else if (this.getCost(fun) == ((Layout) o).getCost(fun)) {
                return 0;
            } else {
                return 1;
            }
        } catch (FlowImpossibleException ex) {
            Logger.getLogger(Layout.class.getName()).log(Level.SEVERE, null, ex);
            return 0;   //TODO: ma ktos lepszy pomysl?!
        }
    }
    
     
    /**
     * Metoda interface'u Comparable. Koszt liczony jest wg domyslnej funkcji.
     * jest uzywana tylko przez algorytm genetyczny.
     * 
     * @param o Do czego jest porownywany biezacy Layout. 
     * @return -1 jezeli biezacy Layout jest tanszy, 1 jezeli drozszy,
     * 0 jezeli ich koszt jest rowny, lub wystapil blad.
     */
     
    public int compareTo(Object o) { 
        return compareTo(o,GeneticSolver.getPreferableCostFunction());
    }
     
   /**
    * Metoda porownuje Layouty na podstawie wybranych usage'ow.
    * 
    */
     
     public boolean contrastWith(Layout l){
         int ok;
        for(int i=0;i<l.size;i++){
         if(this.getPlace(i)==null && l.getPlace(i)==null) ok=1;
         else if(this.getPlace(i) instanceof InboundUsage && l.getPlace(i) instanceof InboundUsage ){
           if(((InboundUsage)this.getPlace(i)).getSourceRiverFacilityID()!=((InboundUsage)l.getPlace(i)).getSourceRiverFacilityID())  ok=0;
            ok=1;
         }
         else if(this.getPlace(i) instanceof OutboundUsage && l.getPlace(i) instanceof OutboundUsage ){
          if(((OutboundUsage)this.getPlace(i)).getTargetRiverFacilityID()!=((OutboundUsage)l.getPlace(i)).getTargetRiverFacilityID())ok=0;
           ok=1;
         }
         else if(this.getPlace(i) instanceof CleaningUsage && (l.getPlace(i) instanceof CleaningUsage) ) ok=1;
         else ok=0;
         if(ok==0) return false;
        }
        return true;
     }
     
    @Override
    public String toString() {
        String s = toString2();
        try{
        String costValue = "   cost: " + this.getCost(CostFunction.getDefault());
        s = s + costValue;
        }
        catch(Exception e)
        {
           return(s + "  NIEPOPRAWNY");
        }
        return s;
    }
    
    public String toString2() {
        String s = "";
        for(int i = 0; i<places.length; i++) {
            if(places[i] == null) s = s+"|-";
            if(places[i] instanceof OutboundUsage) s = s+"|O"+((OutboundUsage)places[i]).getTargetRiverFacilityID();
            if(places[i] instanceof CleaningUsage) s = s+"|M";
            if(places[i] instanceof InboundUsage) s = s+"|I"+((InboundUsage)places[i]).getSourceRiverFacilityID();
        }
        return s;
    }
}
